package me.chan.search;

import static me.chan.util.SortUtil.less;

/**
 * Created by JanGin on 2017/9/26.
 */
public class BinarySearch {

    //base on the sorted array
    public static int binarySearch1(Comparable[] arr, Comparable key) {
        int lo = 0, hi = arr.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2 ;
            if ( arr[mid] == key ) {
                return mid;
            }
            if ( less(arr[mid], key) ) {
                lo = mid + 1;
            } else if ( less(key, arr[mid]) ) {
                hi = mid - 1;
            }
        }
        // return the number of the keys which less than the given key
        return lo;
    }

    //recursive
    public static int binarySearch2(Comparable[] arr, Comparable key, int lo, int hi) {
        if (hi < lo) return lo;

        int mid = lo + (hi - lo) / 2;

        if ( less(arr[mid], key) ) {
            return binarySearch2(arr, key, mid + 1, hi);
        } else if ( less(key, arr[mid]) ) {
            return binarySearch2(arr, key, lo, mid - 1);
        }
        return mid;
    }

    public static void main(String[] args) {
        Comparable[] arr = {1,2,4,7,9,12,45,78};
        int index1 = binarySearch1(arr, 45);
        int index2 = binarySearch2(arr, 45, 0, arr.length - 1);
        System.out.println(index1 == index2);
    }
}
